package year2023.greedy;

import java.util.PriorityQueue;

public class Code03_LessMoneySplitGold {

    /*
    * 一块金条切成两半，是需要花费和长度数值一样的铜板
    * 比如长度为20的金条，不管怎么切，都要花费20个铜板。
    * 一群人想整分整块金条，怎么分最省铜板？
    *
    * 例如，给定数组{10，20，30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分
    * 如果先把长度60的金条分成10和50，花费60，再把长度50的金条分成20和30，花费50，一共花费110铜板
    * 但如果先把长度60的金条分成30和30，花费60，再把长度30的金条分成10和20，花费30，一共花费90铜板
    *
    * 输入一个数组，返回分割的最小代价
    * */

    //暴力
    public static int lessMoney1(int[] arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        return process(arr, 0);
    }

    //等待合并的数，都在arr里，pre之前合并行为产生了多少总代价
    //arr中 只剩一个数字的时候，停止合并，返回总代价
    public static int process(int[] arr, int pre){
        if (arr.length == 1){
            return pre;
        }
        int ans = Integer.MAX_VALUE;
        // arr 0 1 2 3 4...
        //尝试 0~1 0~2 0~3 0~4 0~..  1~2 1~3 1~4 1~...
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++){
                ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
            }
        }
        return ans;
    }

    public static int[] copyAndMergeTwo(int[] arr, int i, int j){
        int[] ans = new int[arr.length - 1];
        int ansi = 0;
        for (int arri = 0; arri < arr.length; arri++) {
            if (arri != i && arri != j){
                ans[ansi++] = arr[arri];
            }
        }
        ans[ansi] = arr[i] + arr[j];
        return ans;
    }

    //贪心
    public static int lessMoney2(int[] arr){
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            pQ.add(arr[i]);
        }
        int sum = 0;
        int cur = 0;
        while (pQ.size() > 1){
            cur = pQ.poll() + pQ.poll();
            sum += cur;
            pQ.add(cur);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {10,30,20};
        System.out.println(lessMoney2(arr));
    }

}
